/*
217080611009 汪边寨
2-29：用穷举法找出1~100的质数并显示出来。分别使用while, do...while,for循环语句实现。
*/
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

//判断是否是质数-for
bool judgePrimeNumberByFor(int n)
{
    if (n == 1)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0)
        return false;
    //不在6的倍数两侧的一定不是质数
    if (n % 6 != 1 && n % 6 != 5)
        return false;

    //在6的倍数两侧的也可能不是质数
    int n2 = sqrt(n);
    for (int i = 5; i <= n2; i += 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
        {
            return false;
        }
    }

    return true;
}

//判断是否是质数-while
bool judgePrimeNumberByWhile(int n)
{
    if (n == 1)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0)
        return false;

    //在6的倍数两侧的也可能不是质数
    int i = 3;
    int n2 = n / 2;
    while (i < n2)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}

//判断是否是质数-do...while
bool judgePrimeNumberByDoWhile(int n)
{
    if (n == 1)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0)
        return false;
    //不在6的倍数两侧的一定不是质数
    if (n % 6 != 1 && n % 6 != 5)
        return false;

    //在6的倍数两侧的也可能不是质数
    int i = 5;
    int n2 = sqrt(n);
    do
    {
        if (n % i == 0 || n % (i + 2) == 0)
        {
            return false;
        }
        i += 6;
    } while (i <= n2);
    return true;
}

//找出两个数之间的质数并显示出来-for
int findPrimeByFor(int min, int max)
{
    int i;
    int count = 0;
    for (i = min; i <= max; i++)
    {
        if (judgePrimeNumberByFor(i))
        {
            cout << "质数:" << i << endl;
            count++;
        }
    }
    return count;
}

//找出两个数之间的质数并显示出来-while
int findPrimeByWhile(int min, int max)
{
    int i = min;
    int count = 0;
    while (i <= max)
    {
        if (judgePrimeNumberByWhile(i))
        {
            cout << "质数:" << i << endl;
            count++;
        }
        i++;
    }
    return count;
}

//找出两个数之间的质数并显示出来-while
int findPrimeByDoWhile(int min, int max)
{
    int i = min;
    int count = 0;
    do
    {
        if (judgePrimeNumberByWhile(i))
        {
            cout << "质数:" << i << endl;
            count++;
        }
        i++;
    } while (i <= max);
    return count;
}

//主函数
int main()
{
    int tstart, tstop;
    int min = 1, max = 100;

    //以for循环方式找到1~100之间的质数，显示如下：
    cout << "以for循环方式找到1~100之间的质数，显示如下：" << endl;
    tstart = clock();
    int count = findPrimeByFor(min, max);
    tstop = clock();
    cout << "找到的质数个数为：" << count << endl;
    cout << "方法(1)时间(ms):" << tstop - tstart << endl;

    //以while循环方式找到1~100之间的质数，显示如下：
    cout << "以while循环方式找到1~100之间的质数，显示如下：" << endl;
    tstart = clock();
    count = findPrimeByWhile(min, max);
    tstop = clock();
    cout << "找到的质数个数为：" << count << endl;
    cout << "方法(2)时间(ms):" << tstop - tstart << endl;

    //以do...while循环方式找到1~100之间的质数，显示如下：
    cout << "以do...while循环方式找到1~100之间的质数，显示如下：" << endl;
    tstart = clock();
    count = findPrimeByDoWhile(min, max);
    tstop = clock();
    cout << "找到的质数个数为：" << count << endl;
    cout << "方法(3)时间(ms):" << tstop - tstart << endl;

    return 0;
}